#include <stdio.h>
#include <stdlib.h>

/* 链表示例程序，使用二级指针 */
typedef struct Student {
  int num;
  float score;
  struct Student *next;
} STU_RECORD;

/* 使用typedef给结构体类型起别名后，可以使用两种方式来表示结构体类型Student：

1. struct Student
2. STU_RECORD

两种表示方式是等价的。
*/

/* 从键盘输入创建链表，将表头指针以函数返回值的形式返回 */
STU_RECORD *create() {
  struct Student *head = NULL;
  struct Student *tail = NULL;
  int num;
  float score;
  scanf("%d", &num);
  scanf("%f", &score);
  while (num != 0) {
    // 为读入的记录创建
    struct Student *n = (struct Student *)malloc(sizeof(struct Student));
    n->num = num;
    n->score = score;
    n->next = NULL;
    if (head == NULL) { // 第一个结点
      head = n;
      tail = n;
    } else {
      tail->next = n;
      tail = n; // 尾指针向后移动
    }
    scanf("%d", &num);
    scanf("%f", &score);
  }
  return head;
}

/* 遍历链表并打印链表内容 */
void print_list(STU_RECORD *head) {
  printf("-----\n");
  STU_RECORD *p = head;
  float sum = 0;
  long count = 0;
  while (p != NULL) {
    printf("ID=%d, score=%.2f\n", p->num, p->score);
    sum += p->score;
    count++;
    p = p->next;
  }
  float avg = sum / count;
  printf("average score: %.2f\n", avg);
  printf("-----\n");
}

/* 删除、释放一个链表，因为删除链表后链表头指针需要重置为NULL，因此使用二级指针的形式 */
void delete_list(struct Student **head_ptr) {
  struct Student *p = *head_ptr;
  while (p != NULL) {
    struct Student *tmp = p;
    p = p->next;
    free(tmp);
    tmp = NULL;
  }
  // 将链表头指针重置为NULL
  *head_ptr = NULL;
}

/* 向链表头节点插入一条记录，因为插入操作会修改链表头指针，因此采用二级指针的形式来修改main函数中的链表头指针 */
void insert_node_at_head(struct Student **head_ptr, int num, float score) {
  // 新建节点
  struct Student *tmp = (struct Student *)malloc(sizeof(struct Student));
  tmp->num = num;
  tmp->score = score;
  tmp->next = NULL;
  // 更新head
  tmp->next = *head_ptr;
  // 修改main函数中的链表头指针，使其指向新的结点
  *head_ptr = tmp;
}

/* 在链表的某个节点后面插入记录，如果没有找到，则在链表尾添加。因为该函数不会修改链表头指针，因此链表头指针可以使用一级指针的形式 */
void insert_after_node(struct Student *head_ptr, int num, float score,
                       int after_num) {
  // 先定位after_num在哪儿
  struct Student *p = head_ptr;
  while (p != NULL) {
    if (after_num == p->num)
      break;
    p = p->next;
  }
  if (p != NULL) {
    // 在p之后插入
    // 新建节点
    struct Student *tmp = (struct Student *)malloc(sizeof(struct Student));
    tmp->num = num;
    tmp->score = score;
    tmp->next = NULL;
    // 加入链表
    tmp->next = p->next;
    p->next = tmp;
  } else {
    // 在链表尾插入，需要先定位到链表尾结点
    struct Student *tail = head_ptr;
    while (tail->next != NULL) {
      tail = tail->next;
    }
    struct Student *tmp = (struct Student *)malloc(sizeof(struct Student));
    tmp->num = num;
    tmp->score = score;
    tmp->next = NULL;
    // 插入表尾
    tail->next = tmp;
  }
}

/* 从链表中删除指定学号num的学生，因为被删除的学生可能存储在链表头结点，删除头结点后需要更新链表头指针 */
void delete_node(struct Student **head_ptr, int num) {
  // 是否删除的是表头？
  if ((*head_ptr)->num == num) { // 要删除表头的情况
    struct Student *tmp = *head_ptr;
    // 更新链表头指针
    *head_ptr = (*head_ptr)->next;
    free(tmp);
    tmp = NULL;
  } else {
    // 待删除的结点一定是位于表头之后
    // 定位prev和p
    struct Student *prev = *head_ptr;
    struct Student *p = prev->next;
    while (p != NULL) {
      if (p->num == num) {
        break;
      }
      prev = p;
      p = p->next;
    }
    if (p != NULL) {
      // 进行删除操作
      prev->next = p->next;
      free(p);
      p = NULL;
    }
  }
}

/* 打印指定学号同学的成绩 */
void print_node(struct Student *head, int num) {
  struct Student *p = head;
  while (p != NULL) {
    if (p->num == num) {
      printf("ID=%d, score=%.2f\n", p->num, p->score);
    }
    p = p->next;
  }
}

int main(int argc, char const *argv[]) {
  struct Student *head;
  printf("创建链表\n");
  head = create();
  printf("The head of the linked list is %p\n", head);
  print_list(head);
  printf("向链表头插入学生记录10111\n");
  insert_node_at_head(&head, 10111, 100.0);
  printf("The head of the linked list is %p\n", head);
  print_list(head);
  printf("向学号为10111的结点之后插入新结点\n");
  insert_after_node(head, 101113, 77, 10111);
  printf("The head of the linked list is %p\n", head);
  print_list(head);
  printf("打印学号为10103的学生的记录\n");
  print_node(head, 10103);
  printf("删除学号为10111的学生的记录\n");
  printf("before: The head of the linked list is %p\n", head);
  delete_node(&head, 10111);
  print_list(head);
  printf("after: The head of the linked list is %p\n", head);
  printf("释放并删除整个链表\n");
  delete_list(&head);
  printf("After delete, head=%p\n", head);
  return 0;
}

/*

测试输入：

10100 100
10101 99
10102 98
10103 97
10104 96
0 0

*/